package com.hyper_yang.algorithmRecord;

public class LeetCode_121 {
//    给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
//    你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
//    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }
    // 方法一: 暴力法
    public static int maxProfit1(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) { // 最后一天可不考虑买入
            for (int j = i; j < prices.length; j++) { // 买后才能卖
                int currentProfit = prices[j] - prices[i];
                maxProfit = Math.max(maxProfit, currentProfit);
            }
        }
        return maxProfit;
    }
    // 方法二: 动态规划
    public static int maxProfit(int[] prices) {
        // 定义状态，保存到目前为止的最小价格，最大利润
        int minPrices = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            minPrices = Math.min(minPrices,prices[i]);
            maxProfit = Math.max(maxProfit,prices[i]-minPrices);
        }

        return maxProfit;
    }
}
